1. Field of the Invention
The present invention relates to communications networks and, more specifically, to multi-service provisioning and restoration functions within multi-layer mesh networks.
2. Description of the Related Art
The process of planning and provisioning bandwidth and capacity in modern large-scale mesh networks is a complicated one, even when one considers only one service that is unprotected. For example, constructing a quality routing solution of LSPs in MPLS networks is an NP-hard combinatorial optimization problem. This involves only the logical layer of the network. For networks with several tens of nodes and links and hundreds of demands, a mathematical optimization problem whose solution produces a feasible, not even optimal, routing and provisioning plan can require millions of variables to allow for possible routing combinations, thus making it mathematically intractable or computationally impractical to solve.
Real-world planning and provisioning problems are inherently much more complex, usually involving multiple services and a heterogeneous mix of protected and unprotected traffic requiring consideration of multiple layers (such as the logical and physical layers) of the network. The computational complexity of such a problem for any realistic sized network makes it impossible to formulate any type of complete end-to-end network planning and provisioning mathematical optimization problem that can be solved in any reasonable timeframe or with any reasonable expectation of quality of results. Faced with the task of solving such a problem, network designers and traffic engineers usually resort to problem decomposition in order to achieve a tractable approach to these complex problems. This includes modeling the problem by resorting to approximations to the real situation that captures the essence of the problem but whose solution does not sacrifice any meaningful characteristics or qualities of the desired solution. Getting quality solutions relies on being able to divide the problem into solvable parts, based on making certain assumptions. Thus, there is a difficult process of problem decomposition and model development to provide tractable subproblems that can be solved separately and, when the solutions are combined, provide meaningful results and a quality overall solution to provisioning of capacity and engineering the traffic in the network.
Additionally, network planning and capacity provisioning in the physical layer practice today is confined to considering protection against single node or link failures. Typically, such failures are assumed to occur randomly in a network, and with nodes configured in such a way that the probability is low of a multiple total node and/or link failure scenario. However, if failures are not necessarily random, such as in orchestrated attacks, or if node or link failures occur at a higher rate than currently assumed, then providing protection against single failures may not be adequate to provide a desired or required level of network availability. Also, critical ultra-high availability services require protection against multiple network failures.
However, due to the previously-mentioned computational complexities, provisioning for protection against multiple node or link failures is not practical and not performed in practice in complete network designs.